<?php

require_once 'util.php';
/*
 * Algo that searches for the longest common subsequences of two sequences.
 * This is not to be confused with the longest common substring problem!!
 *
 * Using Dynamic Programming:
 * Having sequences S and T of length m and n
 *
 * Array L[m][n] to store length of the current longest subsequence at position i,j
 * Starting with L[m][n] = {0}
 *
 * foreach i in m and j in n
 * 		if S[i] == T[j]
 * 			L[i][j] = 1 + max(L[i-1][j], L[i][j-1])
 * 		else
 * 			L[i][j] = max(L[i-1][j], L[i][j-1])
*/

// Two sequences
$S = implode('', generateRandomArray(0, 9, 5));
$T = implode('', generateRandomArray(0, 9, 3));

var_dump( $S );
var_dump( $T );

$longest = longestCommonSubsequence($S, $T);
echo "$longest";

function longestCommonSubsequence( $S, $T ){
	$m = strlen( $S );
	$n = strlen( $T );

	if( 0 >= $m || 0 >= $n ){
		echo "Too short<br/>";
		return 0;
	}

	// Array to store the length values
	$L = array_fill(0, $m+1, array_fill(0, $n+1, 0));

	$longest = 0;

	for( $i=0; $i<=$m; $i++ ){
		for( $j=0; $j<=$n; $j++ ){
			if( $i==0 || $j==0 ){
				$L[$i][$j] = 0;

			}
			else {

				if( $S[$i-1] == $T[$j-1] ){
					$L[$i][$j] = 1 + $L[$i-1][$j-1];
				}
				else {
					$L[$i][$j] = max($L[$i-1][$j], $L[$i][$j-1]);
				}
			}

			echo "{$L[$i][$j]}   ";
			if( $longest < $L[$i][$j] ){
				$longest = $L[$i][$j];
			}
		}
		echo "<br/>";
	}

	echo "Subsequence: " . traceback($L, $S, $T, $m, $n) . "<br/>";

	return $longest;

}

function traceback( $L, $S, $T, $i, $j ){
	if( $i == 0 || $j == 0 ){
		return "";
	}

	if( $S[$i-1] == $T[$j-1] ){
		return traceback($L, $S, $T, $i-1, $j-1) . $S[$i-1];
	}
	else {
		if( $L[$i-1][$j] > $L[$i][$j-1] ){
			return traceback($L, $S, $T, $i-1, $j);
		}
		else {
			return traceback($L, $S, $T, $i, $j-1);
		}
	}
}